import reda.helpers.Helper;

/**
 * 
 */

/**
 * @author reda
 * Time O(nlogn)
 * Space O(n)
 * Stable
 */
public class MergeSort {
	
	public int[] input;
	public int[] result;
	
	public MergeSort(int[] input){
		this.input = input;
		this.result = new int[input.length];
	}
	public void mergeSort(int low, int high){
		if(low>=high){
			return;
		}
		int median = (high + low)/2;
		
		mergeSort(low,median);
		mergeSort(median+1,high);
		merge(low,median,high);
		
	}
	public void merge(int low, int median, int high){
		int i=low,j=median+1,k=low;
		while(i<=median && j<=high){
			while(i<=median && j<=high && input[i]<=input[j]){
				result[k]=input[i]; i++; k++;
			}
			while(i<=median && j<=high && input[j]<input[i]){
				result[k]=input[j]; j++; k++;
			}
		}
		while( i<=median ){
			result[k]=input[i]; i++; k++;
		}
		while( j<=high ){
			result[k]=input[j]; j++; k++;
		}
		for (int h=low; h<=high; h++) {
			input[h] = result[h];
		}
		
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] inputArray = Helper.generateArray(50);
		System.out.println("Before Sort");
		MergeSort m = new MergeSort(inputArray);
		Helper.printer(inputArray);
		m.mergeSort(0,inputArray.length-1);
		System.out.println("\n After Sort");
		Helper.printer(m.result);
	}
}
